/*
958. 二叉树的完全性检验
给定一个二叉树，确定它是否是一个完全二叉树。

思路:
层序遍历: 如果一个节点: 有right没有left， return false
如果一个节点有left没right，或者left right都没有(即左右不全),在上面判断的后序上可以表示为( !left || !right )
则它后面的所有节点都得是叶子节点(没有left和right)
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isCompleteTree = function (root) {
  let isLeaf = false // 是否遍历到叶子节点阶段
  const queue = []
  queue.push(root)
  while (queue.length) {
    const node = queue.shift()
    if (node) {
      const l = node.left
      const r = node.right
      if ((isLeaf && (l || r)) || (!l && r)) {
        return false
      }
      if (l) {
        queue.push(l)
      }
      if (r) {
        queue.push(r)
      } else {
        isLeaf = true
      }
    }
  }
  return true
}
